#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<cstring>
#include<vector>
#include<deque>

using namespace std;

class Solution {
    int f[100010];
public:
    int maxResult(vector<int>& nums, int k) {
        memset(f, -0x3f, sizeof f);
        f[0] = nums[0];
        deque<int> q;
        for (int i = 1; i < nums.size(); i++)
        {
            while (!q.empty() && f[q.back()] < f[i - 1])   q.pop_back();
            q.push_back(i - 1);
            while (!q.empty() && i - q.front() > k)  q.pop_front();
            f[i] = f[q.front()] + nums[i];
        }
        return f[nums.size() - 1];
    }
};